home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Graphics⁄Sound / RTrace-1.0-src / pqueue.c < prev    next >
Text File  |  1992-08-17  |  3KB  |  90 lines
  1. /*
  2.  * Copyright (c) 1988, 1992 Antonio Costa, INESC-Norte.
  3.  * All rights reserved.
  4.  *
  5.  * This code received contributions from the following people:
  6.  *
  7.  *  Roman Kuchkuda      - basic ray tracer
  8.  *  Mark VandeWettering - MTV ray tracer
  9.  *  Augusto Sousa       - overall, shading model
  10.  *
  11.  * Redistribution and use in source and binary forms are permitted
  12.  * provided that the above copyright notice and this paragraph are
  13.  * duplicated in all such forms and that any documentation,
  14.  * advertising materials, and other materials related to such
  15.  * distribution and use acknowledge that the software was developed
  16.  * by Antonio Costa, at INESC-Norte. The name of the author and
  17.  * INESC-Norte may not be used to endorse or promote products derived
  18.  * from this software without specific prior written permission.
  19.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
  20.  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
  21.  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  22.  */
  23. #include "defs.h"
  24. #include "extern.h"
  25.  
  26. /**********************************************************************
  27.  *    RAY TRACING - Priority queue - Version 7.0                      *
  28.  *                                                                    *
  29.  *    MADE BY    : Antonio Costa, INESC-Norte, October 1988           *
  30.  *    ADAPTED BY : Antonio Costa, INESC-Norte, June 1989              *
  31.  *    MODIFIED BY: Antonio Costa, INESC-Norte, July 1990              *
  32.  **********************************************************************/
  33.  
  34. /***** Priority Queue *****/
  35. void
  36. pqueue_insert(key, object)
  37.   real            key;
  38.   object_ptr      object;
  39. {
  40.   REG int         i, j;
  41.  
  42.   REALINC(pqueue_insertions);
  43.   POSINC(pqueue_size);
  44.   if (pqueue_size >= PQUEUE_SIZE_MAX)
  45.     runtime_abort("exhausted PRIORITY QUEUE");
  46.   pqueue[pqueue_size].key = key;
  47.   pqueue[pqueue_size].object = object;
  48.   i = pqueue_size;
  49.   j = i DIV 2;
  50.   while ((i > 1) AND(pqueue[i].key < pqueue[j].key))
  51.   {
  52.     STRUCT_ASSIGN(pqueue[0], pqueue[i]);
  53.     STRUCT_ASSIGN(pqueue[i], pqueue[j]);
  54.     STRUCT_ASSIGN(pqueue[j], pqueue[0]);
  55.     i = j;
  56.     j = i DIV 2;
  57.   }
  58. }
  59. void
  60. pqueue_extract(key, object)
  61.   real           *key;
  62.   object_ptr     *object;
  63. {
  64.   REG int         i, j;
  65.  
  66.   REALINC(pqueue_extractions);
  67.   if (pqueue_size == 0)
  68.     runtime_abort("empty PRIORITY QUEUE");
  69.   *key = pqueue[1].key;
  70.   *object = pqueue[1].object;
  71.   pqueue[1] = pqueue[pqueue_size];
  72.   POSDEC(pqueue_size);
  73.   i = 1;
  74.   while (i + i <= pqueue_size)
  75.   {
  76.     j = i + i;
  77.     if (j != pqueue_size)
  78.       if (pqueue[j].key > pqueue[SUCC(j)].key)
  79.         POSINC(j);
  80.     if (pqueue[i].key > pqueue[j].key)
  81.     {
  82.       STRUCT_ASSIGN(pqueue[0], pqueue[i]);
  83.       STRUCT_ASSIGN(pqueue[i], pqueue[j]);
  84.       STRUCT_ASSIGN(pqueue[j], pqueue[0]);
  85.       i = j;
  86.     } else
  87.       break;
  88.   }
  89. }
  90.